As data storage densities and data transmission rates increase, the ability of hardware devices to correctly recognize binary data diminishes. To ensure data integrity, an error correcting code (ECC) is often used. Many communications systems and data storage systems perform forward error correction (FEC) to improve data transmission accuracy and to ensure data integrity. FEC helps reduce error rates in applications such as data storage, digital video broadcasts, and wireless communications. One type of ECC used for FEC is referred to as error correcting block codes. Block codes are applied to fixed-size blocks of bits or symbols of predetermined size. Examples of block codes include Reed-Solomon (RS), Golay, Bose, Chaudhuri and Hocquenghem (BCH), and Hamming ECC's.
Error correcting block codes may be used in any system in which a first device communicates with a second device via a communications channel. The communications channel can be hardwired or wireless. For example, the communications channel can include one or more of a wireless point-to-point communications link, a wired point-to-point communications link, a wide area network, a local area network, a wireless local area network, a bus, etc. Also, the communications channel could include a storage device having, for example a magnetic storage medium, an optical storage medium, etc. For instance, the first device could be a write channel of a hard disk drive and the second device could be a read channel.
The first device may include an ECC encoder and the second device may include an ECC decoder. The ECC encoder encodes the data before the data is output onto the communications channel. Generally speaking, the ECC encoder inserts redundant symbols into the data. The ECC decoder uses the redundant symbols to detect and, when possible, to correct errors in the received data.
As mentioned above, RS codes are examples of error correcting block codes. The error-correcting ability of any RS code is determined by n−k, the measure of redundancy in the block, where n is the total number of symbols in the block and k is the number of original data symbols. If the locations of the symbols in error are not known in advance, then an RS code can correct up to t=(n−k)/2 erroneous symbols. It is noted that the number of redundant symbols in the block is 2t.
Sometimes error locations are known in advance (e.g., “side information” in demodulator signal-to-noise ratios)—these may be referred to as erasures. An RS code is able to correct twice as many erasures as errors, and any combination of errors and erasures can be corrected as long as the inequality 2E+S<n−k is satisfied, where E is the number of errors and S is the number of erasures in the block.
Given a symbol size s (in bits), the maximum codeword length (n) for an RS code is n=2s−1. For example, the maximum length of a code with 8-bit symbols (s=8) is 255 bytes.
RS codes are computed based on Galois field or finite field mathematics. A finite field has the property that arithmetic operations (+, −, x, /, etc.) on field elements always have a result that is also an element the field. An RS encoder or decoder implements these finite field arithmetic operations.
The properties of Reed-Solomon codes make them especially well-suited to applications where errors occur in bursts because it does not matter to the code how many bits in a symbol are in error—if multiple bits in a symbol are corrupted it only counts as a single error. Conversely, if a data stream is not characterized by error bursts or drop-outs but by random single bit errors, a Reed-Solomon code may not be an optimum choice of ECC.
An RS codeword is generated based on a polynomial referred to as a generator polynomial. In particular, the generator polynomial may be used to generate the redundant symbols for a codeword based on a block of original symbols. The general form of the generator polynomial g(x) is:g(X)=(X−α0)(X−α1) . . . (X−α2t−1)  Equ. 1where X is a variable in the finite field, and αi, for i=0, 2, . . . , 2t−1, are the roots of the generator polynomial. The generator polynomial also can be represented as:g(X)=g0+g1X+g2X2+ . . . g2t−1X2t−1+X2t  Equ. 2where gk, for k=0, 2, . . . , 2t−1, are the coefficients of the generator polynomial.
RS codes are systematic codes, meaning the codeword includes the original message symbols. FIG. 1 is a diagram illustrating an example RS codeword 10 that includes a message portion 12 and a redundant portion 14. The message portion 12 may be represented as a message polynomial m(X), and the redundant portion 14 may be represented as a parity polynomial p(X). The codeword may be represented as a codeword polynomial U(X), where:U(X)=p(X)+Xn−km(X)  Equ. 3
The parity polynomial p(X) (i.e., the redundant symbols) can be determined by dividing Xn−km(X) by the generator polynomial g(X). In particular, the parity polynomial p(X) is the remainder of such a division, and can be expressed as:p(X)=Xn−km(X)mod g(X)  Equ. 4
FIG. 2 is a block diagram of a prior art RS encoder 50. The encoder 50 includes a multiplexer 54 and a multiplexer 58. Additionally, the encoder 50 includes 2t finite field multipliers 62,64, and 2t finite field adders 68, 70. Additionally, the encoder 50 includes 2t registers 74, 76, 78 that are coupled in series. The multiplexer 54 includes a first input that receives the k original symbols d0, d1, . . . , dk-2, dk-1 in sequential order, starting with d0. During calculation of the parity symbols, each original symbol is added with an output of the register 74 and the result is provided as feedback to the registers 74, 76. In particular, for each register 74, 76, 78 the feedback is multiplied by a corresponding coefficient of the generator polynomial. Also, except for the register 78, the output of the multiplier 62, 64 is added with the output of the previous register 76, 78 and then loaded into the register 74, 76. With respect to the register 78, it is loaded with the output of the multiplier 62. Each of the registers 74, 76, 78 includes a clock input which is coupled to a clock signal (not shown).
In operation, the encoder 50 iteratively generates the values of the 2t redundant symbols, and the updated values of the redundant symbols are stored in the registers 74, 76, 78. Initially, the contents of the registers 74, 76, 78 are cleared to zero. Also, the multiplexer 54 is controlled so that its first input is selected. Further, the multiplexer 58 is controlled so that the output of the adder 68 is selected as its output. During a first clock cycle, the symbol d0 is provided to the adder 68, and the output of the adder 68 is operated on by the multipliers 62, 64 and the adders 70. Also, the outputs of the adders 70, when ready, are loaded into the registers 74, 76. Additionally, the output of the multiplier 62 is loaded into the register 78. Similarly, during the subsequent k−1 clock cycles, the remainder of the symbols d1, . . . , dk-2, dk-1 are provided to the adder 58 and results loaded into the registers 74, 76, 78. Thus, during the first k clock cycles, the original symbols appear at the output of the multiplexer 54 and are fed back to the multipliers 62, 64.
The calculations associated with each of the registers 74, 76, 78 can be represented as:rij+1=ri−1j+(dj+r2t−1j)gi  Equ. 5where rij+1 corresponds to the value of the i-th register 74, 76 at the (j+1)-th clock cycle, ri−1j corresponds to the value of the (i−1)-th register 76, 78 at the j-th clock cycle, r2t−1j corresponds to the value of the register 74 at the j-th clock cycle, values of r with negative subscripts and/or negative superscripts are zero, and values of d with negative subscripts are zero. In other words, the value of the i-th redundant symbol at the (j+1)-th iteration (rij+1) is based on the (i−1)-th redundant symbol at the j-th iteration (ri−1j) and the (2t−1)-th redundant symbol at the j-th iteration (r2t−1j)
After all of the k original symbols d0, d1, . . . , dk-2, dk-1 have been operated upon (i.e., after k clock cycles), the 2t redundant symbols are stored in the registers 74, 76, 78. The multiplexer 58 then may be controlled to select its second input, which is coupled to the output of the register 74, as its output. Also, the multiplexer 58 may be controlled to route a zero value to the multipliers 62, 64.
Then, during the next 2t=n−k clock cycles, the 2t redundant symbols are shifted out of the registers 74, 76, 78 and appear at the output of the multiplexer 54.
In the communication channel, one or more of the symbols of a codeword may become corrupted. An RS decoder seeks to correct these errors if possible. Typically, an RS decoder first computes syndrome values for the received codeword. Generally speaking, a syndrome (which includes 2t=n−k syndrome values) is a result of a parity check operation performed on the received codeword to determine if the received codeword is a valid codeword corresponding to the generator polynomial. If all of the syndrome values are zero, then the received codeword is a valid codeword, and there are no errors. If one or more of the syndrome values are non-zero, on the other hand, this indicates that the received codeword is not a valid codeword and that there are one or more errors.
The RS decoder also computes an error locator polynomial based on the syndrome values. The error locator polynomial generally indicates which of the symbols in the received codeword are in error. The error locator polynomial can be calculated using a variety of techniques including a Berlekamp-Massey algorithm (BMA), an inversionless BMA (iBMA) such as described in T. K. Truong et al., “Inversionless Decoding of Both Errors and Erasures of Reed-Solomon Code”, I.E.E.E. Transactions on Communications, Vol. 46, No. 8, August 1998), a Euclidean algorithm, Chien's search technique described in R. T. Chien, “Cyclic Decoding Procedure for the Bose-Chandhuri-Hocquenghem Codes”, I.E.E.E. Transactions on Information Theory, Vol. IT-10, pp. 357 363, October 1964, etc.
Next, the RS decoder may compute an error evaluator polynomial that may be used to correct the detected errors in the received codeword. The error evaluator polynomial is calculated based on the syndrome values and the error locator polynomial using any of a variety of techniques such as Formey's algorithm disclosed in G. D. Formey, “On Decoding BCH Codes”, I.E.E.E Transactions on Information Theory, Vol. IT-11, pp. 549 557, October 1965. Finally, the RS decoder corrects the received codeword using the error evaluator polynomial.
FIG. 3 is a block diagram of a prior art syndrome calculator 100. The syndrome calculator 100 includes 2t finite field adders 104 registers 104 and 2t finite field multiplies 108. Additionally, the syndrome calculator 100 includes 2t registers 112, each having a clock input coupled to a clock signal (not shown). In operation, the registers 112 are initially cleared to zero. Then, symbols of a received codeword v0, v1, . . . , vn−1 are provided to the syndrome calculator 100 in sequential order, one symbol per clock cycle, starting with vn−1. During each clock cycle, the output of each register 112 is multiplied with a corresponding root αi of the generator polynomial g(X) (i=0, 2, . . . , 2t−1). Also, the output of each multiplier 108 is added with the current one of the received symbols v0, v1, . . . , vn−1 by the corresponding adder 104. Further, the output of each of the adders 104 is loaded into the corresponding register 112. After n clock cycles, the 2t syndrome values are stored in the registers 112.